#include <cstdlib>
#include <cstdio>
#include <time.h>


// generate an increasing array a and pick key as one of the a[i]
void
gen_data(std::size_t *a, const std::size_t n, std::size_t& key)
{
  srand ( time(NULL) );

  std::size_t last_val = 0;
  std::size_t i = 0;
  while (i < n)
    {
      std::size_t rep = rand() % (n-i)/2 + 1;
      std::size_t val = last_val + (rand() % 10);

      for (std::size_t j = 0; j < rep; ++j)
	{
	  a[i+j] = val;
	}

      last_val = val;
      i += rep;
    }

  std::size_t pos = rand() % n;
  key = a[pos];
}



std::size_t
find_boundary(std::size_t *a, const std::size_t key, 
	      int low, int high, 
	      bool find_left)
{
  if (low > high)
    {
      return low;
    }

  std::size_t mid = (low + high)/2;
  
  bool go_left;
  if (find_left)
    {
      go_left = (a[mid] >= key);
    }
  else
    {
      go_left = (a[mid] > key);
    }

  if (go_left)
    {
      return find_boundary(a, key, low, mid-1, find_left);
    }
  else
    {
      return find_boundary(a, key, mid+1, high, find_left);
    }
}



int
main(int argc, char* argv[])
{
  std::size_t n;

  if (argc == 1)
    {
      n = 10;
    }
  else
    {
      n = (std::size_t)atoi(argv[1]);
    }

  
  std::size_t a[n];
  std::size_t key;
  gen_data(a, n, key);

  fprintf(stderr, "Generated data: ");
  for (std::size_t i = 0; i < n; ++i)
    {
      fprintf(stderr, "%d ", a[i]);
    }
  fprintf(stderr, "\n");

  std::size_t left = find_boundary(a, key, 0, n-1, true);
  std::size_t right = find_boundary(a, key, 0, n-1, false);

  fprintf(stderr, "Range of %d is [%d, %d)\n", key, left, right);
}
